#include <stdio.h>
#include <stdlib.h>

////////// List implimentation by Linked List //////////

int list_length = 0 ;

struct node
{
 int num ;
 struct node *next ;
} ;

void ll_display(struct node *n)
{
 printf("Present list: [") ;
 while(n != NULL)
 {
  printf(" %d", n->num) ;
  n = n->next ;
 }
 printf(" ]\n") ;
}

struct node *ll_append(struct node *n)
{
 int x ;
 printf("Enter the number: ") ;
 scanf("%d", &x) ;
 if (n == NULL)
 {
  n = malloc(sizeof(struct node));
  n->num = x;
  n->next = NULL;
  list_length++ ;
  return n ;
 }
 else
 {
  struct node *temp, *p ;
  p = n ;
  temp = malloc(sizeof(struct node));
  temp->num = x;
  temp->next = NULL;
  while(p->next!=NULL)
  {
   p = p->next ;
  }
  p->next = temp ;
  list_length++ ;
  return n ;
 }
}

struct node *ll_extend(struct node *n)
{
 int initial, i ;
 struct node *temp= NULL, *p ;
 printf("\nEnter the number of elements in new list: ") ;
 scanf(" %d", &initial) ;
 for(i=0;i<initial;i++)
 {
  printf("\n");
  temp = ll_append(temp) ;
  ll_display(temp);
 }
 p = n ;
 while(p->next != NULL)
 {
  p = p->next ;
 }
 p->next = temp ;
 printf("\nMain list extended!\n") ;
 return n ;
}

struct node *ll_insert(struct node *n)
{
 int index, i, x, flag = 0 ;
 struct node *temp= NULL, *p; 
 printf("\nEnter the index at which you want to insert the number(0-%d): ", list_length) ;
 scanf(" %d",&index) ;
 printf("\nEnter the number: ") ;
 scanf(" %d", &x);
 temp = malloc(sizeof(struct node));
 temp->num = x;
 temp->next = NULL;
 p = n ;
 if(index==0)
 {
  temp->next=p;
  flag=1;
  list_length++;
  return temp;
 }
 else
 {
  for(i=0;;i++)
  {
   if(i==(index-1))
   {
    temp->next=p->next;
    p->next=temp;
    flag=1;
    list_length++;
    break;
   }
   p=p->next;
  }
 }
 if(flag==0)
 {
  printf("\nInvalid Index!!");
 }
 return n;
}

struct node *ll_delete(struct node *n)
{
 struct node *temp= NULL, *p, *current=NULL, *previous=NULL;
 int choice, i, index, x, flag=0;
 printf("\n Delete menu:") ;
 printf("\n 1. Delete by index\n 2. Delete by number") ;
 printf("\n Enter Your Choice(0 to Exit): ") ;
 scanf(" %d",&choice);
 p = n ;
 switch(choice)
 {
  case 1: printf("\nEnter the index which you want to delete(0-%d): ", list_length-1) ;
          scanf(" %d",&index) ;
          if(index==0)
          {
           p=p->next;
           flag=1;
           list_length-- ;
           return p;
          }
          else
          {
           current=p;previous=NULL;
           for(i=1;i<=index;i++)
           {
            previous=current;
            current=current->next;
           }
           previous->next=current->next;
           free(current);
           flag=1;
           list_length-- ;
           return p;
          }
          if(flag==0)
          {
           printf("\nInvalid index!");
           return n;
          }
          break;
  case 2: printf("\nEnter the number which you want to delete: ", list_length-1) ;
          scanf(" %d",&x) ;
          for(current=p,previous=NULL;current!=NULL && (current->num)!=x;previous=current,current=current->next);
          {
           if(current==NULL)
           {
            flag=1;
            return p;
           }
           else
           {
            if(previous==NULL)
            {
             p=p->next;
             flag=1;
             list_length-- ;
             return p;
            } 
            else
            {
             previous->next=current->next;
             free(current);
             flag=1;
             list_length-- ;
             return p;
            }
           }
          }
          if(flag==0)
          {
           printf("\nNumber Not Found!!");
           return n;
          } 
          break;
  default: break;
 }
 return n ;
}

struct node *ll_indexval(struct node *n)
{
 int index, i, x, flag = 0 ;
 struct node *p;
 p=n;
 printf("\nEnter the index(0-%d): ", list_length-1) ;
 scanf(" %d",&index) ;
 if(index==0)
 {
  printf("\n The element at index %d is %d.\n", index, p->num);
 }
 else
 {
  if(index>0 && index<(list_length-1))
  {
   for(i=0;i<index;i++)
   {
    p = p->next;
   }
   printf("\n The element at index %d is %d.", index, p->num);
  }
  else
  {
   printf("\nInvalid Index!!");
  }
 }
 return n ;
}

struct node *ll_sort(struct node *n)
{
 int i,j,x;
 struct node *p;
 struct node *t;
 p=n;
 for(i=1;i<list_length;i++)
 {
  t=p->next;
  for(j=i+1;j<=list_length;j++)
  {
   if(p->num > t->num)
   {
    x=p->num;
    p->num=t->num;
    t->num=x;
   }
   t=t->next;
  }
  p=p->next;
 }
 return n ;
}


struct node *ll_reverse(struct node *n)
{
 struct node *c,*p,*reversed;
 c = malloc(sizeof(struct node));
 c->num=n->num;
 c->next=NULL;
 p=c;
 n=n->next;
 while(n!=NULL)
 {
  reversed=malloc(sizeof(struct node));
  reversed->num=n->num;
  reversed->next=p;
  p=reversed;
  n=n->next;
 }
 return reversed;
}

void ll_maxval(struct node *n)
{
 int max_no;
 max_no = n->num;
 while((n->next)!=NULL)
 {
  if((n->num)>max_no)
  {
   max_no=n->num;
  }
  n=n->next;
 }
 printf("\nMaximum number is:%d\n",max_no);
}

void ll_minval(struct node *n)
{
 int min_no;
 min_no=n->num;
 while((n->next)!=NULL)
 {
  if((n->num)<min_no)
  {
   min_no=n->num;
  }
  n=n->next;
 }
 printf("\nMinimum number is:%d\n",min_no);
}


void ll_impliment()
{
 struct node *end = NULL;
 int number, i, initial, choice;
 char c ;
 printf("\nList intialization: ") ;
 printf("\nEnter the number of elements: ") ;
 scanf(" %d", &initial) ;
 for(i=0;i<initial;i++)
 {
  printf("\n");
  end = ll_append(end) ;
  ll_display(end);
 }
 do
 {
  printf("\n\n\t LINKED LIST MENU\n") ;
  printf("\n 1. Append\n 2. Extend\n 3. Insert\n 4. Delete\n 5. Index\n 6. Max\n 7. Min\n 8. Reverse\n 9. Sort");
  printf("\n Enter Your Choice(0 to Exit): ") ;
  scanf(" %d",&choice);
  switch(choice)
  {
   case 1: end = ll_append(end);
           break;
   case 2: end = ll_extend(end);
           break;
   case 3: end = ll_insert(end);
           break;
   case 4: end = ll_delete(end);
           break;
   case 5: end = ll_indexval(end);
           break;
   case 6: ll_maxval(end);
           break;
   case 7: ll_minval(end);
           break;
   case 8: end = ll_reverse(end);
           break;
   case 9: end = ll_sort(end);
           break;
   default: break;
  }
  ll_display(end);
  if(choice!=0)
  {
   printf("\nInput any character to continue ") ;
   scanf(" %s",&c);
  }
 } while(choice) ;
}

////////// List Implimentation by Dynamic Arrays //////////

int array_size, *array_list ;

void arr_append()
{
 int x ;
 printf("Enter number to append");
 scanf("%d",&x);
 array_size++;
 array_list=realloc(array_list,(array_size+1)* sizeof(*array_list));
 array_list[array_size]=x;
}

void arr_extend()
{
 int i, *t, s;
 printf("\nEnter no. of elements you would like to Extend in the List");
 scanf("%d",&s);
 t=malloc((s)*sizeof(*t));
 printf("\nEnter the inputs: ");
 for(i=0;i<s;i++)
 {
  scanf(" %d",&t[i]);
 }
 array_list=realloc(array_list,(array_size+s+1)*sizeof(*array_list));
 for(i=0;i<s;i++)
 {
  array_size++;
  array_list[array_size]=t[i];
 }
}

void arr_insert()
{
 int i,x, index;
 printf("Enter Position");
 scanf(" %d",&index);
 if(index<=array_size+1)
 {
  printf("Enter the number");
  scanf("%d",&x);
  array_list=realloc(array_list,(array_size+1)*sizeof(*array_list));
  for(i=array_size;i>=(index-1);i--)
  {
   array_list[i+1]=array_list[i];
  }
  array_list[index-1]=x;
  array_size++;
 }
 else
 {
  printf("Invalid Position!!!");
 }
}

void arr_display()
{
 int i;
 printf("\nThe Current List is [ ");
 for(i=0;i<=array_size;i++)
 {
  printf("%d ",array_list[i]);
 }
  printf("]\n");
}

void arr_remove()
{
 int i,flag,x;
 flag = 0 ;
 printf("\nEnter number to be removed");
 scanf("%d",&x);
 for(i=0;i<=array_size;i++)
 {
  if(array_list[i]==x)
  {
   flag = 1 ;
   while(i<array_size)
   {
    array_list[i]=array_list[i+1];
    i++;
   }
   array_list=realloc(array_list,(array_size)*sizeof(*array_list));
   array_size--;
   break;
  }
 }
 if(flag==0)
 {
  printf("\nNumber Not Found!!!") ;
 }
}

void arr_indexremove()
{
 int i,x,index;
 printf("Enter index to be removed(0-%d):", array_size);
 scanf("%d",&index);
 if(index<=array_size && index>=0)
 {
  x=array_list[index];
  for(i=index;i<array_size;i++)
  {
   array_list[i]=array_list[i+1];
  }
  array_size--;
  array_list=realloc(array_list,array_size*sizeof(*array_list));
  printf("\nThe Element %d, Removed!",x);
 } 
 else
 {
  printf("\nInvalid Index!!!");
 }        
}

void arr_index()
{
 int index ;
 printf("\nEnter Index(0-%d):", array_size);
 scanf("%d",&index);
 if(index<=array_size)
 {
  printf("\nElement at position %d is %d",index,array_list[index]);
 }
 else
 {
  printf("\nInvalid Index!!!");
 }
}

void arr_sort()
{
 int i,j;
 for(i=0;i<=array_size-1;i++)
 {
  for(j=i+1;j<=array_size;j++)
  {
   if(array_list[i]>array_list[j])
   {
    array_list[i]=array_list[i]+array_list[j];
    array_list[j]=array_list[i]-array_list[j];
    array_list[i]=array_list[i]-array_list[j];
   }
  }
 }
}

void arr_reverse()
{
 int i,j;
 for(i=0,j=array_size;i<j;i++,j--)
 {
  array_list[i]=array_list[i]+array_list[j];
  array_list[j]=array_list[i]-array_list[j];
  array_list[i]=array_list[i]-array_list[j];
 }
}

void arr_counter()
{
 int i,ctr,x;
 ctr = 0 ;
 printf("\nEnter Integer to be counted: ");
 scanf("%d",&x);
 for(i=0;i<=array_size;i++)
 {
  if(array_list[i]==x)
  ctr++;
 }
 printf("\nThe integer %d appears in the array %d times.", x, ctr) ;
}

void arr_impliment()
{
 int choice, i;
 char c ;
 printf("\nList Initialization:");
 printf("\nEnter no. of elements: ");
 scanf("%d",&array_size);
 array_size = array_size-1;
 array_list=malloc((array_size+1)* sizeof(*array_list));
 printf("\nEnter the inputs: ");
 for(i=0;i<=array_size;i++)
 {
  scanf(" %d",&array_list[i]);
 }
 choice=1 ;
 do
 {
  printf("\n\t Dynamic Array List Menu\n\t=========================") ;
  printf("\n 1. Append\n 2. Extend\n 3. Insert\n 4. Remove\n 5. Pop\n 6. Index\n 7. Count\n 8. Sort\n 9. Reverse");
  printf("\n Enter Your Choice(0 to Exit): ") ;
  scanf(" %d",&choice);
  switch(choice)
  {
   case 1: arr_append();
           break;
   case 2: arr_extend();
           break;
   case 3: arr_insert();
           break;
   case 4: arr_remove();
           break;
   case 5: arr_indexremove();
           break;
   case 6: arr_index();
           break;
   case 7: arr_counter();
           break;
   case 8: arr_sort();
           break;
   case 9: arr_reverse();
           break;
   default: break;
  }
  arr_display();
  if(choice!=0)
  {
   printf("\nInput any character to continue ") ;
   scanf(" %s",&c);
  }
 }while(choice);
}

////////// Main() Function //////////

void main()
{
 int choice ;
  printf("\n\t Main Menu\n\t###########\n") ;
  printf("\n 1) Linked List Implimentation\n 2) Dynamic Array Implimentation");
  printf("\n Enter Your Choice(0 to Exit): ") ;
  scanf(" %d",&choice);
  switch(choice)
  {
   case 1: ll_impliment();
           break;
   case 2: arr_impliment();
           break;
   default: break;
  }
}
